package sort;

public class MergeSort {

    //递归实现归并排序
    public static void mergeSort(int[] array,int left,int right){
        if (left >= right){
            return;
        }
        int mid = (left+right)/2;
        mergeSort(array,left,mid);
        mergeSort(array,mid+1,right);
        merge(array,left,right,mid);

    }
    //对排序好的数据进行合并
    public static void merge(int[] array,int start,int end,int mid){
        int s1 = start;
        int s2 = mid+1;
        int[] tmp = new int[end-start+1];
        int k = 0;
        while (s1 <= mid && s2 <= end ){
            if(array[s1] > array[s2]){
                tmp[k++] = array[s2++];
            }else {
                tmp[k++] = array[s1++];
            }
        }
        while (s1 <= mid){
            tmp[k++] = array[s1++];
        }
        while (s2 <= end){
            tmp[k++] = array[s2++];
        }
        for (int i = 0; i < tmp.length; i++) {
            array[i+start] = tmp[i];
        }
    }
}
